package com.douma._2022_6_29;

import java.util.Scanner;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class 事件推送 {

    // 第一种方法：暴力解法
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();
        int R = sc.nextInt();
        int[] A = new int[m];
        for (int i = 0; i < m; i++) {
            A[i] = sc.nextInt();
        }
        int[] B = new int[n];
        for (int i = 0; i < n; i++) {
            B[i] = sc.nextInt();
        }

        // 时间复杂度为 O(mn)，不符合题意，因为题目的输入数据规模为 1 <= n, m <= 100000
        // 如果时间复杂度为 O(mn) 的话，这个算法会超时
        // 对于时间复杂度和输入数据规模的关系，请参考课程 B【刷题篇第 0 天：刷题前准备】 第 5 小节：https://appvpmptkl94774.pc.xiaoe-tech.com/detail/p_6233f79fe4b066e9609122bc/6
        // 遍历 A 中每一个元素
        for (int i = 0; i < m; i++) {
            int ai = A[i];
            int minDis = Integer.MAX_VALUE;
            // 这里将 bj 设置为一个不可能的值，因为 bj 最大值为 1000000000，所以设置为 1000000001
            int bj = 1000000001;
            // 针对 A 中的每个元素，再遍历 B 的每个元素
            for (int j = 0; j < n; j++) {
                int b = B[j];
                // 找到符合：① Ai <= Bj 且 ② Ai、Bj 之间的距离小于等于 R
                if (ai <= b && Math.abs(ai - b) <= R) {
                    // 得到距离最近的 Bj
                    if (Math.abs(i - j) < minDis) {
                        minDis = Math.abs(i - j);
                        bj = b;
                    }
                }
            }

            if (minDis != Integer.MAX_VALUE) {
                System.out.println(ai + " " + bj);
            }
        }

        sc.close();
    }

    // 第二种方法：二分查找
    // 因为两个输入数组都是有序的，在有序的数组中查找元素，可以往二分查找算法想
    // 时间复杂度 O(mlogn)
    // 如果你不熟悉二分查找，请学习课程 B【刷题篇第 8 天：二分查找】 中的第 1 节到第 26 节的内容
    // 链接：https://appvpmptkl94774.pc.xiaoe-tech.com/detail/p_62369fd1e4b0f7cb7c7435f6/6
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();
        int R = sc.nextInt();
        int[] A = new int[m];
        for (int i = 0; i < m; i++) {
            A[i] = sc.nextInt();
        }
        int[] B = new int[n];
        for (int i = 0; i < n; i++) {
            B[i] = sc.nextInt();
        }

        // 遍历 A 中每一个元素
        for (int i = 0; i < m; i++) {
            int ai = A[i];
            // 如果 i 大于 B 数组的长度
            if (i > n) {
                // 那么直接计算左边 [0...n - 1] 符合条件的最后一个 bj
                int leftIndex = lastTarget(B, 0, n - 1, ai, R);
                if (leftIndex != -1) {
                    System.out.println(ai + " " + B[leftIndex]);
                    continue;
                }
            } else {
                // 先判断 i == j 的情况
                int j = i;
                int bj = B[j];
                if (ai <= bj && Math.abs(ai - bj) <= R) {
                    System.out.println(ai + " " + bj);
                    continue;
                }
                // 计算左边 [0...i - 1] 符合条件的最后一个 bj
                int leftIndex = lastTarget(B, 0, i - 1, ai, R);
                // 计算右边 [i + 1...n - 1] 符合条件的第一个 bj
                int rightIndex = firstTarget(B, i + 1, n - 1, ai, R);
                if (leftIndex != -1 && rightIndex != -1) {
                    if (Math.abs(leftIndex - i) <= Math.abs(rightIndex - i)) {
                        System.out.println(ai + " " + B[leftIndex]);
                    } else {
                        System.out.println(ai + " " + B[rightIndex]);
                    }
                } else if (leftIndex != -1) {
                    System.out.println(ai + " " + B[leftIndex]);
                } else if (rightIndex != -1) {
                    System.out.println(ai + " " + B[rightIndex]);
                }
            }
        }

        sc.close();
    }

    // 在数组 B 的区间 [left...right] 中查找最后一个符合条件的 bj ，并返回它的索引
    private static int lastTarget(int[] B, int left, int right, int ai, int R) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            int b = B[mid];
            if (ai <= b && Math.abs(ai - b) <= R) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        int b = B[left];
        if (ai <= b && Math.abs(ai - b) <= R) return left;
        return -1;
    }

    // 在数组 B 的区间 [left...right] 中查找第一个符合条件的 bj ，并返回它的索引
    private static int firstTarget(int[] B, int left, int right, int ai, int R) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            int b = B[mid];
            if (ai <= b && Math.abs(ai - b) <= R) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        int b = B[left];
        if (ai <= b && Math.abs(ai - b) <= R) return left;
        return -1;
    }
}
